


from bisect import bisect_left
# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
def longest_increasing_subsequence(nums):
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return tails

nums = [8, 9, 10, 1, 2, 3, 4]  # 3, 4
print(longest_increasing_subsequence(nums))  # 输出应为6



'''

我们可以通过这个具体的例子nums = [8, 9, 10, 1, 2, 3, 4]来逐步理解代码的执行过程。

初始化：

tails = []，现在tails为空。
遍历nums数组的第一个元素8：

pos = bisect_left(tails, 8)，因为tails为空，所以pos = 0。
pos == len(tails)，tails更新为[8]。
遍历nums数组的第二个元素9：

pos = bisect_left(tails, 9)，在tails中找到第一个大于等于9的位置是1，所以pos = 1。
pos == len(tails)，tails更新为[8, 9]。
遍历nums数组的第三个元素10：

pos = bisect_left(tails, 10)，在tails中找到第一个大于等于10的位置是2，所以pos = 2。
pos == len(tails)，tails更新为[8, 9, 10]。
遍历nums数组的第四个元素1：

pos = bisect_left(tails, 1)，在tails中找到第一个大于等于1的位置是0，所以pos = 0。
pos不等于len(tails)，所以更新tails[0] = 1，现在tails = [1, 9, 10]。
遍历nums数组的第五个元素2：

pos = bisect_left(tails, 2)，在tails中找到第一个大于等于2的位置是1，所以pos = 1。
pos不等于len(tails)，所以更新tails[1] = 2，现在tails = [1, 2, 10]。
遍历nums数组的第六个元素3：

pos = bisect_left(tails, 3)，在tails中找到第一个大于等于3的位置是2，所以pos = 2。
pos不等于len(tails)，所以更新tails[2] = 3，现在tails = [1, 2, 3]。
遍历nums数组的第七个元素4：

pos = bisect_left(tails, 4)，在tails中找到第一个大于等于4的位置是3，所以pos = 3。
pos == len(tails)，tails更新为[1, 2, 3, 4]。
最终，tails数组变为[1, 2, 3, 4]。从这个tails数组可以看出，它的长度4就是输入数组nums中的最长递增子序列的长度，而且tails数组中的元素[1, 2, 3, 4]构成了一个可能的最长递增子序列。

通过这个具体例子，我们可以观察到tails数组是如何在遍历过程中动态更新的，以及如何通过二分查找和贪心策略来高效地找到最长递增子序列的。
'''



# 
from bisect import bisect_left

def longest_increasing_subsequence(nums):
    if not nums:
        return []

    tails = [nums[0]]
    # 存储在每个位置结束的最长递增子序列
    sequences = [[num] for num in nums]
    
    for num in nums[1:]:
        # 使用二分查找找到适当的位置
        pos = bisect_left(tails, num)
        
        if pos == len(tails):
            tails.append(num)
            # 如果是新的尾部，我们可以简单地添加之前的序列并追加当前数字
            sequences.append(sequences[pos-1] + [num])
        else:
            tails[pos] = num
            # 更新当前位置的最长递增子序列
            if pos > 0:
                sequences[pos] = sequences[pos-1] + [num]
            else:
                sequences[pos] = [num]
        print(sequences)
                
    # 返回最后一个序列，它是最长的
    return sequences[-1]

nums = [8, 9, 10, 1, 2]
print(longest_increasing_subsequence(nums))  # 输出应为[8, 9, 10]